只出现一次的数字

发表于 | 分类于 |
字数统计: 348 字 | 阅读时长 ≈ 1 分钟

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

方法一：位运算

^ 异或运算符功能

  • 任何数和自己做异或运算，结果为 0，即 a⊕a=0。
  • 任何数和 0 做异或运算，结果还是自己，即 a⊕0=a。
  • 异或运算中，满足交换律和结合律，也就是a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

所以出现两次的字母异或运算得0，跟出现一次的字母异或运算得到自己

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
  public int singleNumber(int[] nums) {
    int single = 0;
    for(int num: nums) {
      single ^= num;
    }
    return single;
  }
}

var singleNumber = function(nums) {
  let item = 0
    for(let num of nums) {
      item ^= num
    }
  return item
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
  • 空间复杂度：O(1)。

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：38.6 MB, 在所有 Java 提交中击败了51.47%的用户